Prodotto cartesiano, relazioni

Dati due insiemi $A$ e $B$ e degli elementi $a\in A$ e $b\in B$, sappiamo che è possibile costruire l'insieme $\left\{ a,\, b\right\}$.
Se vogliamo un insieme che ricordi che $a$ è da considerare per primo e $b$ per secondo, allora l'insieme $\left\{ a,\, b\right\}$ non va bene, perché $\left\{ a,\, b\right\} =\left\{ b,\, a\right\}$ (hanno gli stessi elementi). Per essere più precisi, vogliamo poter costruire per ogni $a\in A$ e $b\in B$ un insieme ${\bf {(a,\, b)}}$ (che chiameremo coppia ordinata) in modo tale che si abbia:

$$(a,\, b)=(a^{'},\, b^{'})\; \Longleftrightarrow \; (a=a^{'} \textrm{ e } b=b^{'})$$

e tale che dalla coppia sia ricavabile il primo ed il secondo termine. Un modo, per niente ovvio, è quello di porre la seguente:

Definizione 2.3.1   La coppia ordinata con termini $a$ e $b$ è l'insieme:

$$(a,\, b)=\left\{ \left\{ a\right\},\, \left\{ a,\, b\right\}\right\} .$$

Definizione 2.3.2   L'insieme di tutte le possibili coppie con primo termine in $A$ e secondo termine in $B$ è chiamato prodotto cartesiano di $A$ e $B$ ed è indicato con:

$$% latex2html id marker 225 {\bf {A\times B}}= \left\{ x:\exists \, a\in A\; e \; \exists \, b\in B:x=(a,\, b)\right\}$$

$=\left\{ (a,\, b):a\in A,\, b\in B\right\}$.

Esempio 2.3.3   Se $A=\left\{ a_1,\, a_2,\, a_3,\, a_4,\, a_5 \right\}$ e $B=\left\{ b_1,\, b_2,\, b_3,\, b_4 \right\}$, il prodotto cartesiano $A\times B$ si può rappresentare con il rettangolo:

$$\begin{tabular}{r\vert c\vert c\vert c\vert c\vert c\vert} ... ...1)$\ & $(a_4,b_1)$\ & $(a_5,b_1)$\ \\ \hline \end{tabular}$$

Possiamo addirittura omettere l'indicazione delle coppie e decidere, ad esempio, che la casella all'incrocio di $a_3$ e $b_2$ rappresenti la coppia $(a_3,b_2)$.

Una relazione tra gli elementi di $A$ e gli elementi di $B$ dal punto di vista logico è un predicato di due variabili $\mathcal{R}(x,\, y)$, in cui $x$ si fa variare solo tra gli elementi di $A$ e $y$ solo fra gli elementi di $B$. Una relazione logica $\mathcal{R}$ tra $A$ e $B$ individua un sottoinsieme del prodotto cartesiano:

$$% latex2html id marker 240 R=\left\{ (a,\, b)\in A\times B: \mathcal{R} (a, \, b) \textrm{ \\lq e vera }\right\} .$$

Esempio 2.3.4   Sia $A=\left\{ a_1,\, a_2,\, a_3,\, a_4,\, a_5 \right\}$ l'insieme delle aule di una facoltà e $B=\left\{ b_1,\, b_2,\, b_3,\, b_4 \right\}$ le ore di lezione di una data mattina. Consideriamo la relazione $\mathcal{R} (x, \, y)=$ ''l'aula $x$ all'ora $y$ è occupata'', per rappresentare tutte le possibili aule occupate alle varie ore. Possiamo usare una tabella del tipo:

$$% latex2html id marker 246 \begin{tabular}{r\vert c\vert c... ... & $\times$\ & $\times$\ & $\times$\\ \hline \end{tabular}$$

dove le caselle con la crocetta rappresentano le coppie $(a,\, b)$ che verificano la relazione, cioè tali che l'aula $a$ è occupata all'ora $b$.

La relazione logica $\mathcal{R}$ tra $A$ e $B$ di solito ha un suo significato ed è definita mediante una ben precisa costruzione simbolica, perciò contiene molta più informazione dell'insieme $R\subset A\times B$ che si limita a registrare quando $\mathcal{R}$ è verificata. Tuttavia, se assumiamo il punto di vista che ciò che importa della relazione $\mathcal{R}$ si riduce a ciò che può dirci di vero o di falso sulle coppie $(a,\, b)$, allora $R$ può sostituire $\mathcal{R}$ come relazione tra $A$ e $B$. Questa considerazione equivale ad affermare che due relazioni $\mathcal{R}$ e $\mathcal{R^{'}}$ tra $A$ e $B$, che sono vere (false) nelle stesse coppie non sono distinguibili. Questo è l'atteggiamento giusto per la teoria degli insiemi, che non suppone l'esistenza a priori di relazioni matematiche, ma si propone di definirle come insiemi, senza riceverle da altre teorie esterne. Viceversa, un qualunque sottinsieme $R\subset A\times B$ definisce una relazione $\mathcal{R}$ (magari senza un particolare significato):

$$\mathcal{R} (x,\, y)=\left(x\in A\textrm{ e }y\in B\textrm{ e }(x,\, y)\in R\right) .$$

È per questo che poniamo la seguente

Definizione 2.3.5   Definiamo relazione tra ${\bf A}$ e ${\bf B}$ un qualunque sottoinsieme $R$ di $A\times B$.

D'ora in poi, identificheremo $\mathcal{R}$ con $R$ e quindi scriveremo indifferentemente $(a,\, b)\in R$ oppure $\mathcal{R}(a,\, b)$ è vera; scriveremo a volte anche $a\, R\, b$ in luogo di $(a,\, b)\in R$.

Definizione 2.3.6   Sia $A$ un insieme. Una relazione $R\subset A\times A$ tra $A$ e se stesso si dice una relazione di equivalenza se valgono le seguenti proprietà:

1. $\forall \, a\in A: \; (a,\, a)\in R$ (proprietà riflessiva);
2. $\forall \, a,\, b\in A: \; (a,\, b)\in R\; \Rightarrow \; (b,\, a)\in R$ (proprietà simmetrica);
3. $\forall \, a,\, b,\, c\in A: \; (a,\, b)\in R$ e $(b,\, c)\in R\; \Rightarrow \; (a,\, c)\in R$ (proprietà transitiva).

Osservazione 2.3.7   Se adoperiamo il simbolo $\sim \; =\; \sim_{R}$ invece di $R$ e scriviamo $a\sim b$ invece di $(a,\, b)\in \; \sim$, le proprietà precedenti si scrivono in modo più suggestivo:

1. $\forall \, a\in A: \; a\sim a$;
2. $\forall \, a,\, b\in A: \; a\sim b\; \Rightarrow \; b\sim a$;
3. $\forall \, a,\, b,\, c\in A: \; a\sim b$ e $b\sim c \; \Rightarrow \; a\sim c$.

Esempio 2.3.8   Sia $A=\left\{ \textsl{rette del piano euclideo}\right\}$ e sia

$$% latex2html id marker 286 R=\left\{ (a,\, b)\in A\times A... ...tsl{ con } a=b \textsl{ oppure } a\cap b=\emptyset \right\}$$

la relazione di ''parallelismo'' fra rette. Allora

1. è automaticamente verificata;
2. è verificata perché le relazioni $a=b$ oppure $a\cap b=\emptyset$ sono simmetriche;
3. si hanno quattro possibilità:

   i)

   $a=b$ e $b=c$; allora $a=c$ e $3.$ è provata;

   ii)

   $a=b$ e $b\cap c=\emptyset$; allora $a\cap c=\emptyset$ e $3.$ è provata;

   iii)

   $a\cap b=\emptyset$ e $b=c$; analoga alla ii);

   iv)

   $a\cap b=\emptyset$ e $b\cap c=\emptyset$; se inoltre $a=c$, allora $3.$ è provata, mentre, se $a\neq c$, allora $a,\, b,\, c$ sono tre rette distinte con $a/\! \! /b$ e $b/\! \! /c$; sappiamo allora dalla geometria euclidea del piano che $a/\! \! /c$, cioè $a\cap c=\emptyset$.

Quando si assegna una relazione di equivalenza $R$ su un insieme $A$, l'insieme risulta suddiviso in tanti sottoinsiemi:

Definizione 2.3.9   Sia $A$ un insieme, $R$ una relazione di equivalenza su $A$ ed $a$ un elemento di $A$; si dice classe di equivalenza di $a$ il seguente sottoinsieme di $A$:

$${\bf {[a]}}=\left\{ b\in A: \, b\sim_{R} a\right\} ,$$

che raccoglie tutti gli elementi di $A$ equivalenti all'elemento $a$.

Osservazione 2.3.10   $\;$

1. $[a]=[b]\; \Leftrightarrow a\sim b$;
2. $a\nsim b \Leftrightarrow [a]\cap [b]=\emptyset$;

Perciò due classi di equivalenza o sono uguali o sono disgiunte.

Definizione 2.3.11   Sia $A$ un insieme, $R$ una relazione di equivalenza su $A$. L'insieme di tutte le classi di equivalenza di $A$ (rispetto ad $R$):

$$\left\{ [a];\, a\in A\right\}$$

si dice insieme quoziente di $A$ (rispetto ad $R$) e si indica con $A/R$.

È possibile trovare un insieme $I$ (insieme degli indici) ed associare ad ogni elemento $i\in I$ una classe di equivalenza $C_i$ di $A$ rispetto ad $R$ in modo tale che:

1. $C_i=C_j$ se e solo se $i=j$;
2. per ogni classe di equivalenza $C=[a]$ di $A$ rispetto ad $R$, esiste un $i\in I$ (ed uno solo) tale che $C=C_i$.

Allora la famiglia di insiemi $\left\{ C_i\right\}_{i\in I}$ coincide con $A/R$ e verifica:

1. $i\neq j \; \Rightarrow \; C_i\cap C_j=\emptyset$;
2. $${\bigcup_{i\in I}}C_i=\left\{ x:\exists \, i\in I \textrm{ con }x\in C_i\right\}=A$$;
3. $A\neq \emptyset \Longrightarrow \forall \, i\in I : C_i$ non è vuoto.

Definizione 2.3.12   Sia $A$ un insieme e $\mathcal{B}=\left\{ B_i\right\}_{i\in I}$ una famiglia di sottoinsieme di $A$ indicizzata dall'insieme $I$; diremo che $\mathcal{B}$ è una partizione di $A$ se valgono le seguenti proprietà:

1. i $B_i$ sono tutti non vuoti se $A$ è non vuoto;
2. i $B_i$ sono a due a due disgiunti;
3. $${\bigcup_{i\in I}}B_i=A$$.

Una relazione $R$ di equivalenza su $A$ definisce una partizione di $A$ nelle sue classi di equivalenza; viceversa, data una partizione $\mathcal{B}=\left\{ B_i\right\}_{i\in I}$ di $A$, è possibile definire una relazione di equivalenza $R$ su $A$ (indotta da $\mathcal{B}$) ponendo:

$$a\, R\, b\; \Longleftrightarrow \; \exists \, i\in I :a,\, b\in B_i.$$

Non è difficile verificare che la relazione $R$ è effettivamente una relazione di equivalenza e che le sue classi di equivalenza sono tutti e soli i sottoinsiemi $\left\{ B_i\right\}$ della partizione.

Inoltre la corrispondenza:

$$\left\{ relazioni \; di\; equivalenza\; su\; A \right\} \longleftrightarrow \left\{ partizioni\; di\; A\right\}$$

tra relazioni di equivalenza e partizioni è biunivoca, nel senso che :

1. se $R$ è una relazione di equivalenza su $A$, $\mathcal{B}_R$ è la partizione indotta da $R$ e $R_{\mathcal{B}_R}$ è la relazione definita da $\mathcal{B}_R$, allora $R=R_{\mathcal{B}_R}$;
2. se $\mathcal{B}$ è una partizione di $A$, $R_{\mathcal{B}}$ è la relazione definita da $\mathcal{B}$ e $\mathcal{B}_{R_{\mathcal{B}}}$ è la partizione indotta da $R_{\mathcal{B}}$, allora $\mathcal{B}=\mathcal{B}_{R_{\mathcal{B}}}$.

Esempio 2.3.13   Torniamo a considerare l'insieme:

$$A=\left\{ \textsl{rette del piano}\right\} ,$$

con la relazione di equivalenza $/\! \! /$ data dal parallelismo (d'ora in poi, $r/\! \! /s$ non escluderà $r=s$, anzi, per noi se $r=s$, allora certamente si ha $r/\! \! /s$). Una classe di equivalenza è costituita da tutte le rette parallele tra loro (o parallele ad una retta assegnata). Possiamo dire che due rette sono nella stessa classe di equivalenza se e solo se hanno la stessa direzione. Viceversa, se $D$ è l'insieme delle ''direzioni delle rette del piano'' e per ogni $d\in D$ poniamo:

$$B_d=\left\{ r\in A:r\textsl{ ha la direzione }d\right\} ,$$

otteniamo una partizione $\left\{ B_d\right\}_{d\in D}$ di $A$ che coincide con la partizione dovuta alla relazione di equivalenza data dal parallelismo.

Nell'esempio precedente si suppone di sapere già che cosa è la direzione di una retta e di saper decidere se due rette hanno la stessa direzione. Possiamo decidere, invece, di non sapere cosa sono le direzioni e decidere di ''inventarle'' affermando che le ''direzioni'' sono le classi di equivalenza di rette parallele. In questo modo una ''direzione'' viene ad essere un insieme ed anche se questo risulta innaturale è però molto vantaggioso.
La relazione che afferma che $r$ ed $s$ hanno la stessa direzione diventa allora la relazione: $r$ ed $s$ stanno nello stesso insieme ''direzione''.

Esempio 2.3.14   Sia $A=[0,\, 1]$ l'intervallo chiuso dei numeri reali tra $0$ e $1$; se vogliamo costruire un nuovo insieme in cui i numeri $0$ ed $1$, e solo loro, siano identificati, possiamo ricorrere alla relazione di equivalenza così definita:

$$x\sim y \Longleftrightarrow \left\{ \begin{array}{ll} x=y ... ...extsl{oppure}\\ x=1 \textsl{ e }y=0 & \end{array} \right.$$

A questa relazione corrisponde la seguente partizione:

$$\mathcal{B}=\left\{ \left\{ x\right\} \right\}_{x\in (0,\, 1)}\cup \left\{ 0,\, 1\right\}$$

e quindi l'insieme quoziente $A/\sim$ ha tanti elementi quanti sono i numeri $x$ in $(0,\, 1)$, e in più ha l'elemento $\left\{ 0,\, 1\right\}$ che rappresenta l'elemento ottenuto ''incollando'' $0$ e $1$.

Definizione 2.3.15   Sia $A$ un insieme ed $R\subset A\times A$ una relazione tra gli elementi di $A$; si dice che $R$ è una relazione d'ordine ( debole o parziale) se verifica le seguenti proprietà:

OD1)

${\forall \,}a\in A\; \left( (a,\, a)\in R\right)$ (proprietà riflessiva);

OD2)

${\forall \,}a,\, b\in A\; \left( (a,\, b)\in R \textsl{ e }(b,\, a)\in R\; \Rightarrow a=b\right)$ (proprietà antisimmetrica);

OD3)

${\forall \,}a,\, b,\, c\in A\; \left( (a,\, b)\in R \textsl{ e }(b,\, c)\in R\; \Rightarrow (a,\, c)\in R\right)$ (proprietà transitiva).

Osservazione 2.3.16   Se indichiamo $R$ con il simbolo ${\leqslant}$ e scriviamo $a {\leqslant}b$ invece di $(a,\, b)\in \, {\leqslant}$, le tre proprietà date sopra acquistano la seguente forma:

OD1)

${\forall \,}a\in A\; (a\, {\leqslant}\; a)$;

OD2)

${\forall \,}a,\, b\in A\; \left( (a\, {\leqslant}\; b) \textsl{ e }(b \, {\leqslant} \, a)\; \Rightarrow a=b\right)$;

OD3)

${\forall \,}a,\, b,\, c\in A\; \left( (a\, {\leqslant}\; b) \textsl{ e }(b\, {\leqslant}\; c)\; \Rightarrow a\, {\leqslant}\; c\right)$.

Il simbolo ${\leqslant}$ si legge ''minore o uguale'' come per l'ordinamento naturale dei numeri reali, ma può non avere niente a che fare con l'ordinamento naturale, persino nel caso in cui $A$ sia $\mathbb {R}$ o un suo sottoinsieme.

Definizione 2.3.17   Sia $A$ un insieme e ${\leqslant}$ un ordinamento (debole) su $A$. L'ordinamento ${\leqslant}$ si dice totale se vale inoltre la proprietà:

$\! \! OD$4) ${\forall \,}a,\, b\in A\; (a\, {\leqslant}\; b \textsl{ oppure }b \, {\leqslant}\; a)$.

Definizione 2.3.18   Sia $A$ un insieme e ${\leqslant}$ un ordinamento debole su $A$. La relazione così definita:

$$a<b \; \Longleftrightarrow \; (a\, {\leqslant}\; b \textsl{ e } a\neq b)$$

si dice l' ordinamento stretto definito da ${\leqslant}$.

Osservazione 2.3.19   L'ordinamento stretto $<$ verifica le seguenti due proprietà:

OS1)

${\forall \,}a\in A\; (a \nless a)$;

OS2)

${\forall \,}a,\, b,\, c\in A\; \left( (a<b) \textsl{ e }(b<c)\; \Rightarrow a<c\right)$.

Osservazione 2.3.20   $\;$

1. L'ordinamento debole ${\leqslant}$ si ottiene dall'ordinamento stretto $<$ così
   
   $$a\, {\leqslant}\; b\; \Longleftrightarrow \; (a=b \textsl{ oppure } a<b);$$
   
   

2. Se $<$ è una relazione su $A$ che verifica le proprietà OS1) e OS2), allora definisce una relazione d'ordine debole ${\leqslant}$ con le proprietà OD1), OD2) e OD3);
3. La relazione di ordine debole ${\leqslant}$ è totale se e solo se la relazione di ordine stretto $<$ verifica la seguente proprietà:
   $OS$3) ${\forall \,}a,\, b\in A\; \left( (a<b)\textsc{ aut }(a<b)\textsc{aut}(b<a)\right)$.

Una relazione di ordine debole con la proprietà OS3) si dirà totale.

Osservazione 2.3.21   La corrispondenza tra ordinamenti deboli e stretti su $A$:

$$\left\{ \textrm{ ordinamenti deboli di }A \right\} \longlef... ...htarrow \left\{ \textrm{ ordinamenti stretti di } A\right\}$$

è biunivoca e cosìla corrispondenza:

$$\left\{ \textrm{ ordinamenti deboli, totali di }A \right\} ... ...left\{ \textrm{ ordinamenti stretti, totali di }A\right\} .$$

Definizione 2.3.22   Sia $A$ un insieme e ${\leqslant}$ un ordinamento totale su $A$. Un elemento $a$ si dice un minimo di $A$ se:

$${\forall \,}b\in A\; ( a\, {\leqslant}\; b);$$

si dice un massimo di $A$ se:

$${\forall \,}b\in A \; (b\, {\leqslant}\; a);$$

Osservazione 2.3.23   Un insieme $A$ con un ordinamento ${\leqslant}$ può non avere né massimo né minimo, ma se ha un massimo (o un minimo) questo è unico e possiamo indicarli con:

$${\bf max} (A)=\max (A,\, {\leqslant}) \textsl{ e } {\bf min} (A)=\min (A,\, {\leqslant}).$$

Definizione 2.3.24   Sia $A$ un insieme e ${\leqslant}$ un ordinamento debole su $A$. Un elemento $a$ di $A$ si dice un elemento minimale di $A$ se:

$${\forall \,}b\in A\; ( b\, {\leqslant}\; a \; \Longrightarrow \; b=a);$$

si dice un elemento massimale di $A$ se:

$${\forall \,}b\in A\; ( a\, {\leqslant}\; b\; \Longrightarrow \; b=a);$$

Osservazione 2.3.25   $\;$

1. Un minimo (massimo) è un elemento minimale (massimale); in generale non è vero il viceversa;
2. un insieme con un ordinamento debole può avere diversi elementi minimali e diversi elementi massimali.

Esempio 2.3.26   Sia $A$ l'insieme dei ''punti della lettera $W$'', ordinati nel modo seguente:

$$a\, {\leqslant}\; b \; \Longleftrightarrow \left\{ \begin... ...po }a\textsl{ si pu\\lq o incontrare }b.\\ \end{array} \right.$$

Questo insieme ha due elementi minimali e quattro elementi massimali, nessun minimo e nessun massimo.

Definizione 2.3.27   Se $A$ è un insieme con un ordinamento ${\leqslant}$ e $B$ è un sottoinsieme di $A$, allora gli elementi di $B$ ricevono un ordinamento dall'ordinamento di $A$ ( ordinamento indotto da $A$ con ${\leqslant}$ su $B$).

In termini di insiemi, l'ordinamento indotto è l'insieme:

$$% latex2html id marker 496 (\, {\leqslant}\; )\cap (B\times B).$$

Un sottonisieme $B$ di $A$ può avere elementi minimi, massimi, minimali o massimali indipendentemente da $A$.

Definizione 2.3.28   Un insieme $A$ con un ordinamento ${\leqslant}$ si dice bene ordinato se ogni suo sottoinsieme non vuoto ha minimo.

Esempio 2.3.29   $\;$

1. Si può dimostrare (ma non è per niente facile) che $\mathbb {N}$ con l'ordinamento naturale è bene ordinato;
2. L'insieme $\mathbb {Z}$ degli interi con l'ordinamento naturale non è bene ordinato;
3. $\mathbb {R}$ con l'ordinamento naturale non è bene ordinato;
4. $A=\left\{ 1-\displaystyle{\frac{1}{n}}\right\}_{n\in \mathbb {N}^{+}} \cup \left\{ 2-\frac{1}{n}\right\}_{n\in \mathbb {N}^{+}}$ con l'ordinamento indotto da $\mathbb {R}$ è bene ordinato;
5. $A=\left\{ \displaystyle{\frac{1}{n}}\right\}_{n\in \mathbb {N}^{+}} \cup \left\{ 0\right\}$ con l'ordinamento indotto da $\mathbb {R}$ non è bene ordinato;

Osservazione 2.3.30   $\;$

1. Un insieme bene ordinato $A$ è anche totalmente ordinato perché presi comunque due elementi $a$ e $b$ di $A$ uno dei due deve essere il minimo per il sottoinsieme $\left\{ a,\, b\right\}$ e quindi deve aversi $a\, {\leqslant}\; b$ oppure $b\, {\leqslant} \, a$.
2. Sia $A$ un insieme bene ordinato con l'ordinamento ${\leqslant}$; se su $A$ consideriamo l'ordinamento inverso di ${\leqslant}$ definito ponendo:
   
   $$a\, {\preccurlyeq}\, b \; \Longleftrightarrow \; b\, {\leqslant}\; a,$$
   
   
   non è detto che $A$ con l'ordinamento ${\preccurlyeq}$ sia ancora bene ordinato (sebbene sia totalmente ordinato): ad esempio, $\mathbb {N}$ con l'ordinamento inverso dell'ordinamento naturale non è bene ordinato.

Definizione 2.3.31   Sia $A$ un insieme con un buon ordinamento ${\leqslant}$; per ogni elemento $a\in A$ (che non sia l'eventuale massimo di $A$) chiameremo successivo di $a$ in $A$ l'elemento:

$${\bf s}(a)= \min \left\{ b\in A: b>a\right\} .$$

Esempio 2.3.32   $\;$

1. In $\mathbb {N}$ (con l'ordinamento naturale) il successivo di ogni $n\in \mathbb {N}$ è dato dall'elemento $n+1$;
2. la nozione di successivo di un elemento è definibile anche in $\mathbb {Z}$ (con l'ordinamento naturale), pur non essendo $\mathbb {Z}$ bene ordinato;
3. In $\mathbb {R}$ (con l'ordinamento naturale) non è definibile il successivo di alcun elemento.